'''
https://leetcode.cn/problems/alien-dictionary/description
'''
from collections import deque
from typing import List


class Solution:
    def alienOrder(self, words: List[str]) -> str:
        graph = [[] for _ in range(26)]
        indegree = [-1] * 26
        for word in words:
            for char in word:
                indegree[ord(char) - ord('a')] = 0

        for i in range(len(words) - 1):
            a, b = words[i], words[i + 1]
            for j in range(min(len(a), len(b))):
                if a[j] != b[j]:
                    graph[ord(a[j]) - ord('a')].append(ord(b[j]) - ord('a'))
                    indegree[ord(b[j]) - ord('a')] += 1
                    break
            else:
                if len(a) > len(b):
                    return ''

        kind = sum(1 for c in range(26) if indegree[c] != -1)
        q = deque([c for c in range(26) if indegree[c] == 0])
        res = ""
        while q:
            u = q.popleft()
            res += chr(u + ord('a'))
            for v in graph[u]:
                indegree[v] -= 1
                if indegree[v] == 0:
                    q.append(v)
        return res if len(res) == kind else ""
